/**415. 字符串相加
 * - 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
 */
export function addStrings(num1: string, num2: string): string {
    const length = Math.max(num1.length, num2.length)
    num1 = num1.padStart(length, '0')
    num2 = num2.padStart(length, '0')
    let res = ''
    let carry = 0
    for (let i = length - 1; i >= 0; i--) {
        const sum = Number(num1[i]) + Number(num2[i]) + carry
        res = (sum % 10) + res
        carry = Math.floor(sum / 10)
    }
    if (carry) res = carry + res
    return res
};

/**43. 字符串相乘
 * - 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 
 * - 不是最优解
 */
export function multiply(num1: string, num2: string): string {
    if (num1 === '0' || num2 === '0') return '0'
    /**单一数字和完整数字相乘。数字1是一个正常数字，数字2只有一位 */
    const smallMultiply = (n1: string, n2: string) => {
        let res = ''
        let carry = 0
        for (let i = n1.length - 1; i >= 0; i--) {
            const product = Number(n2) * Number(n1[i]) + carry
            res = (product % 10) + res
            carry = Math.floor(product / 10)
        }
        if (carry) res = carry + res
        return res
    }
    /**大数字相加 */
    const add = (n1: string, n2: string) => {
        const length = Math.max(n1.length, n2.length)
        n1 = n1.padStart(length, '0')
        n2 = n2.padStart(length, '0')
        let res = ''
        let carry = 0
        for (let i = length - 1; i >= 0; i--) {
            const sum = Number(n2[i]) + Number(n1[i]) + carry
            res = (sum % 10) + res
            carry = Math.floor(sum / 10)
        }
        if (carry) res = carry + res
        return res
    }
    let res = ''
    //按照乘法列竖式的方法，把每个数字相乘  
    for (let i = num2.length - 1; i >= 0; i--) {
        const product = smallMultiply(num1, num2[i])
        const realProduct = product.padEnd((product.length - 1) + (num2.length - i), '0')//需要往末尾补0，才是真正的和，补充的个数就看数字在哪个位置 
        res = add(res, realProduct)
    }
    return res
}